package set.src;

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

import set.CMDR.SnapshotCounter;

/**
 * 
 * @author Erik Sapir & Lior Zibi
 * 
 * Optimistic List implementation: first find element in list,
 * than lock and validate element still in list and are adjacent.
 * 
 * @param T Item type.
 */
public class OptimisticList<T> implements Set<T>{
	/**
	 * First list entry
	 */
	volatile private Node m_head;
  
	/**
	 * counter for number of element in the list
	 */
	volatile private SnapshotCounter m_counter;
    
	/**
	 * Constructor
	 */
	public OptimisticList(int numOfThreads) {
		System.out.println("\n\tSet Is: Optimistic List\n");
		
		// Add sentinels to start and end
		this.m_head  = new Node(Integer.MIN_VALUE);
		this.m_head.m_next = new Node(Integer.MAX_VALUE);
    
		m_counter = new SnapshotCounter(numOfThreads);
	}
	
	public boolean add(T item, int threadID) {
		SnapshotCounter pToCounter = m_counter;
		int key = item.hashCode();
		
		while (true) {
			Node pred = this.m_head;
			Node curr = pred.m_next;
      
			//search for first element equal or larger than new element
			while (curr.m_key < key) {
				pred = curr; curr = curr.m_next;
			}
		
			//lock  both pred and curr
			pred.lock(); curr.lock();
      
			try {
				//make sure pred and curr still in list and that pred.next = curr
				if (validate(pred, curr)) {
					if (curr.m_key == key) {
						//element already in list - nothing to add
						return false;
					} else {               
						// add new element to list
						Node entry = new Node(item);
						entry.m_next = curr;
						pred.m_next = entry;
                      
						//element added successfully - increment number of elements in list
						pToCounter.inc(threadID);
            
						return true;
					}
				}
			} finally {               
				pred.unlock(); curr.unlock();  // always unlock
			}
		}
	}
  
	public boolean remove(T item, int threadID) {
		SnapshotCounter pToCounter = m_counter;
		int key = item.hashCode();
		
		while (true) {
			Node pred = this.m_head;
			Node curr = pred.m_next;
			
			//search for first element equal or larger than element to remove
			while (curr.m_key < key) {
				pred = curr; curr = curr.m_next;
			}
			
			//lock both pred and curr
			pred.lock(); curr.lock();
			
			try {
				//make sure pred and curr still in list and that pred.next = curr
				if (validate(pred, curr)) {
					if (curr.m_key == key) { 
						// remove element from list
						pred.m_next = curr.m_next;
						
						//element removed successfully - decrement number of elements in list
						pToCounter.dec(threadID);
            
						return true;
					} else {               
						// element not in list - nothing to remove
						return false;
					}
				}
			} finally {                
				pred.unlock(); curr.unlock(); // always unlock
			}
		}
	}
  
	public boolean contains(T item, int threadID) {
		int key = item.hashCode();
		
		while (true) {
			Node pred = this.m_head; // sentinel node;
			Node curr = pred.m_next;
			
			//search for first element equal or larger than element we are searching
			while (curr.m_key < key) {
				pred = curr; curr = curr.m_next;
			}
			
			//lock both pred and curr
			pred.lock(); curr.lock();
			
			try {
				//make sure pred and curr still in list and that pred.next = curr
				if (validate(pred, curr)) {
					//return true iff element found in list
					return (curr.m_key == key);
				}
			} finally {                
				pred.unlock(); curr.unlock(); // always unlock
			}
		}
	}
  
	public void clean(int threadID) {
		m_head.lock();
		Node curr = m_head.m_next;
		
		try {
			
			//go over all elements in list and remove them.
			while (curr.m_key != Integer.MAX_VALUE){
				curr.lock();
				
				try {
					m_head.m_next = curr.m_next;  // remove
                 
					//element removed successfully - decrement number of elements in list
					m_counter.dec(threadID);
				
				} finally {
					curr.unlock(); //always unlock
				}
				
				curr = m_head.m_next;
			
			}
		} finally {
			m_head.unlock(); //always unlock
		}
	}
	
	public boolean isEmpty(int threadID) {
		
		//lock head and head.next and check if nead.next in the tail of set
		m_head.lock();
	
		try {	
			m_head.m_next.lock();
		
			try	{
				//list is empty iff head pointing to tail
				return (m_head.m_next.m_key == Integer.MAX_VALUE);
			}
			finally	{			
				m_head.m_next.unlock(); //always unlock
			}
		}
		
		finally	{		
			m_head.unlock(); //always unlock
		}
	}

	public int size(int threadID) {
		return m_counter.scan_sum();
	}

  
	/**
	 * Check that prev and curr are still in list and adjacent
     * @param pred predecessor node
     * @param curr current node
     * @return whether predecessor and current have changed
     */
	private boolean validate(Node pred, Node curr) {
		Node entry = m_head;

		while (entry.m_key <= pred.m_key) {
			if (entry == pred)
				return pred.m_next == curr;
			entry = entry.m_next;
		}
		
		return false;
	}
	
	/**
	 * list entry
	 */
	private class Node {
		/**
		 * actual item
		 */
		final T m_item;
		
		/**
		 * item's hash code
		 */
		final int m_key;
		
		/**
		 * next entry in list
		 */
		volatile Node m_next;
    
		/**
		 * Synchronizes node.
		 */
		Lock m_lock;
		
		/**
		 * Constructor for usual entry
		 * @param item element in list
		 */
		Node(T item) {
			this.m_item = item;
			this.m_key = item.hashCode();
			m_lock = new ReentrantLock();
		}
		
		/**
		 * Constructor for sentinel entry
		 * @param key should be min or max int value
		 */
		Node(int key) {
			this.m_key = key;
			this.m_item = null;
			m_lock = new ReentrantLock();
		}

		/**
		 * Lock node
		 */
		void lock() {m_lock.lock();}
		
		/**
		 * Unlock node
		 */
		void unlock() {m_lock.unlock();}
	}
}
